package leetcode3;

import java.util.*;


class CQueue {

    private Stack stack;

    public CQueue() {
        stack = new Stack<>();
    }
    //归还图书
    public void appendTail(int value) {

    }

    //借书
    public int deleteHead() {
        return -1;
    }
}
public class Day7 {

    public int[] topKFrequent(int[] nums, int k) {
        if(nums.length <= k) {
            return nums;
        }
        Map<Integer,Integer> map = new HashMap<>();
        for(int x:nums) {
            if(map.getOrDefault(x,-1) == -1) {
                map.put(x,1);
            }else {
                map.put(x,map.get(x)+1);
            }
        }
        PriorityQueue<int[]> queue = new PriorityQueue<>(new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return o1[1] - o2[1];
            }
        });
        //按照map中的value进行比较
        for(Map.Entry<Integer,Integer> tmp:map.entrySet()) {
            int key = tmp.getKey(),val = tmp.getValue();
            if(queue.size() == k) {
                if(queue.peek()[1] < val) {
                    queue.poll();
                    queue.add(new int[]{key,val});
                }
            }else {
                queue.add(new int[]{key,val});
            }
        }
        int[] ret = new int[k];
        for(int i=0;i<k;i++) {
            ret[i]=queue.poll()[0];
        }
        return ret;
    }



    public boolean isValid(String s) {
        Stack<Character> stack = new Stack<>();
        //左括号入栈，右括号出栈
        for(int i=0;i<s.length();i++) {
            char ch = s.charAt(i);
            if(ch =='(' || ch=='[' || ch=='{') {
                stack.push(ch);
            }else {
                if(stack.isEmpty()) return false;
                char top = stack.pop();
                if(top == '(') {
                    if(ch!=')') return false;
                }else if(top == '[') {
                    if(ch!=']') return false;
                }else if(top=='{') {
                    if(ch!='}') return false;
                }
            }
        }
        return stack.isEmpty()?true:false;
    }


}
